#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int> > &matrix) {
            vector<int> ans;
            if (matrix.size() == 0) return ans;
            int i = 0, j = 0;
            int m = matrix.size();
            int n = matrix[0].size();
            while(i <= m-i-1 && j <= n-j-1) {
				if (i == m-i-1) {
                    for (int col = j; col < n-j; col++)
					    ans.push_back(matrix[i][col]);
                }
			    else if (j == n-j-1) {
				    for (int row = i; row < m-i; row++)
					    ans.push_back(matrix[row][j]);
			    } else {
                    for (int col  = j; col < n - j; col++)
                        ans.push_back(matrix[i][col]);
                    for (int row = i+1; row < m - i; row++)
                        ans.push_back(matrix[row][n-j-1]);
                    for (int col = n- j-2; col >= j; col--)
                        ans.push_back(matrix[m-1-i][col]);
                    for (int row = m-i-2; row > i; row--)
                        ans.push_back( matrix[row][j]);
			    }
                i++;
                j++;
			}
            return ans;
        }
};

//add better code
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> ans;
        if (matrix.size() == 0) return ans;
        int left, right, top, down;
        left = 0;
        right = matrix[0].size()-1;
        top = 0;
        down = matrix.size()-1;
        while(left <= right && top <= down) {
            for (int i = left; i <= right; i++) {
                ans.push_back(matrix[top][i]); 
            }   
            for (int i = top+1; i <= down; i++) {
                ans.push_back(matrix[i][right]);
            }   
            for (int i = right-1; i >= left && top != down; i--) {
                ans.push_back(matrix[down][i]);
            }   
            for (int i = down-1; i > top && left != right; i--) {
                ans.push_back(matrix[i][left]);
            }   
            left++;
            right--;
            top++;
            down--;
        }
        
        return ans;
    }
};


//test on 1337 online test and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;
    cout << "-----------------Test 1--------------------" << endl;
    int A[4][3] = {{1,2,3},{4,5,6},{7,8,9},{10,11,12}};
    vector<vector<int> > matrix(3, vector<int>(3, 0));
    vector<vector<int> > matrix1;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            matrix[i][j] = A[i][j];
	vector<int> test;

	test.push_back(1);
	test.push_back(2);
	test.push_back(3);
	matrix1.push_back(test);
    mySolution.spiralOrder(matrix);
    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
